package com.lsa.cormen.ch15.samples;

import java.util.Arrays;

import junit.framework.Assert;
import junit.framework.TestCase;

public class SubsetSumTest extends TestCase {
    public void testSubsetSum2() {
        Integer[] taken = SubsetSum.subsetSumByDp(5842, new int[] { 267, 493,
                869, 961, 1000, 1153, 1246, 1598, 1766, 1922 }); // knapsack,
                                                                 // weights
        Assert.assertTrue(Arrays.equals(new Integer[] { 2, 3, 4, 6, 8 }, taken));
    }

//    OOM    
//    public void testSubsetSum3() {
//        Integer[] taken = SubsetSum.subsetSumByDp(2463098, new int[] { 518533,
//                1037066, 2074132, 1648264, 796528, 1593056, 686112, 1372224,
//                244448, 488896, 977792, 1955584, 1411168, 322336, 644672,
//                1289344, 78688, 157376, 314752, 629504, 1259008 }); // knapsack,
//                                                                    // weights
//        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 4, 19 }, taken));
//    }

    public void testSubsetSum4() {
        Integer[] taken = SubsetSum.subsetSumByDp(50, new int[] { 41, 34, 21,
                20, 8, 7, 7, 4, 3, 3 }); // knapsack, weights
        Assert.assertTrue(Arrays.equals(new Integer[] { 2, 4, 5, 6, 7, 9 },
                taken));
    }

    public void testSubsetSum5() {
        Integer[] taken = SubsetSum.subsetSumByDp(100, new int[] { 81, 80, 43,
                40, 30, 26, 12, 11, 9 }); // knapsack, weights
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 7, 8 }, taken));
    }

    public void testSubsetSum6() {
        Integer[] taken = SubsetSum.subsetSumByDp(22, new int[] { 1, 2, 4, 8,
                16, 32 }); // knapsack, weights
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 2, 4 }, taken));
    }

    public void testSubsetSum7() {
        Integer[] taken = SubsetSum.subsetSumByDp(50, new int[] { 25, 27, 3,
                12, 6, 15, 9, 30, 21, 19 }); // knapsack, weights
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 4, 9 }, taken));
    }

}
